\documentclass[a4paper,12pt]{article}
\usepackage{xspace}
\usepackage{graphicx,amssymb,amstext,amsmath,setspace,enumerate}
% For writing algorithm
\usepackage{algorithmic, algorithm}
% Easy way to format the page
\usepackage{multicol} \usepackage{booktabs} \usepackage[margin=1in,
vmargin={1cm,1cm},includehead,includefoot]{geometry}
\usepackage{ifthen}

\newenvironment{modsec}[1]
{\noindent \textbf{#1}
  \renewcommand{\arraystretch}{1.2}
  \begin{table}[htb!]
    \centering
    \begin{tabular}{p{3cm}p{10cm}}
}
{\end{tabular}\end{table}}


% \onehalfspacing
\doublespacing 
\newcommand{\M}{$M$}
\newtheorem{proposition}{Proposition}[section]
\newcommand{\zip}{z_{\it UFL}}
\newcommand{\zlp}{z_{\it RUFL}}
\newcommand{\Omg}{\Omega}
\newcommand{\omg}{\omega}
%\newcommand{\bigm}{} 
\newcommand{\cm}{\tilde{M}}
\newcommand{\st}{\text{s.t.}\xspace}

\begin{document}
\section*{The transportation problem with random demand}
\begin{modsec}{Sets}
  $I$ & set $i \in I$ suppliers \\
  $J$ & set $j \in J$ customers \\
  $\Omg$ & set $\omg \in \Omg$ scenarios
\end{modsec}

\begin{modsec}{Data}
  $c_{ij} $  & transportation cost from $i$ to $j$ \\
  $W_i$   & capacity of $i$ \\
  $p^{\omg}$ & probability of scenario $\omg$ \\
\end{modsec}

\begin{modsec}{Random Variables}
  $d_j^\omg $& demand of $j$ in scenario $\omg$ \\  
  $M_j^\omg$ & big m coefficient \\
  $\cm_j^\omg$ & cheated big m coefficient 
\end{modsec}

\begin{modsec}{Decision Variables}
  $x_{ij}$ & the amount shipped from $i$ to $j$\\
  $y^\omg$ & indicator variable of scenario $\omg$  
\end{modsec}

\noindent
\textbf{Formulation I (Chance Constraints Program or CCP) }
\begin{align*}
  \min \quad & \sum_{i,j} c_{ij} x_{ij} \\
  \st  \quad &  \sum_j x_{ij} \le W_i && \forall i \in I \\
             & P\left\{ \sum_i x_{ij} \ge \tilde{d}_j , \forall j \in
               J \right\} \ge 1 - \epsilon \\
             & x_{ij} \ge 0 && \forall i \in I, j\in J             
\end{align*}
\noindent
\textbf{Formulation II ( Mixed Integer Program or MIP) }
\begin{align*}
  \min   \quad &  \sum_{i,j} c_{ij} x_{ij} \\
  \st    \quad &  \sum_j x_{ij} \le W_i && \forall i \in I \\
               & \sum_i x_{ij} - d_j^\omg \ge M_j^\omg (1 -
               y^\omg) && \forall j \in J, \omg \in \Omg, \\
               & \sum_{\omg} p^\omg y^\omg \ge 1 - \epsilon \\
               & x_{ij} \ge 0 && \forall i \in I, j\in J \\
               & y^\omg \in \{0,1\} && \forall \omg \in \Omg
\end{align*}

\section*{Computational Experience}
We randomly generate instances ranging $|I|,|J|$ from 10
to 50 and $\omg$ from 30 to 40. $\epsilon = 0.2$ for all instances. 
The sizes of the instances are intentionally chosen to be small
. This is because we need to get the exact optimal solution $x_{ij}^*$s
by solving
the MIP with $M_j^\omg = d_j^\omg$ to compute $\cm_j^\omg $'s, where 
\begin{equation*}
  \cm_j^\omg = |\sum_i x_{ij}^* - d_j^\omg|.
\end{equation*} 
All scenarios occur with $p^\omg = 1/|\Omega|$.
Transportation cost is chosen from $U(0,1)$.
Random demand has normal distribution s.t. $\tilde{d} \sim N(1,
0.1)$. In order to make the problem feasible, we choose the capacity $W_i \sim N(|J| /
|I| + 2, 0.2)$. CPLEX 12.1 is used as the MIP solver along with Python
API and we customize
the following parameters with the associated explanation
\begin{itemize}
\item \textbf{CPX\_PARAM\_CUTSFACTOR = 1.0} : all algorithm will be based on
  pure branch and bound algorithm and therefore all cuts are turned
  off. (Even if we allow cuts generation, few cuts are generated at
  the root node and no cuts are generated in other nodes. More
  experiments and analysis need to be done on this phenomenon.)
\item \textbf{CPX\_PARAM\_HEURFREQ = -1} : We overlook the influence
  by heuristic solutions.
\item \textbf{CPX\_PARAM\_PREIND = 0} : Preprocessing is turned off in order to
  maintain the purity of big M coefficients in the formulation. In
  other words, CPLEX is not allowed to modify the coefficients in the
  data it is given.
\item \textbf{CPX\_PARAM\_THREADS = 1} : Parallelism is not considered for the
  moment, therefore we use only a single thread.
\item \textbf{CPX\_PARAM\_ADVIND = 0} : This setting is important. We ensure
  that all instances, especially the ones formulated with the cheated
  big M,  are solved from scratch. The issue is that when we modify
  the big M coefficient and resolve the problem, the basis inherited
  from previous solving gives advantage of solving the problem 
  with cheated big-M. This is a REAL cheat and must be avoided for a
  fair comparison. An alternative is to dump all the
  instances as .lp files and then let CPLEX read in them and then
  solve. The problem is that the data structures, such as row and
  column indices, are harder to manipulate. And when we move to our
  adaptive branch and bound algorithm, we always start from scratch
  by setting small big M values without knowing the true solutions. In
  that case, we will have a fair comparison and reading from .lp files
  become awkward.  
\end{itemize}


\section*{Results}
We explain the headers of the following tables. $|\Omg|, |I|, |J|$ are
the cardinality of the corresponding sets. obj1, obj2 are the objective values
of instances with big-M and cheated big-M respectively. time1 and
time2 are the elapsed time in two cases. nit1 and nit2 are the number
of iterations. nnd1 and nnd2 are the processed nodes.

\begin{table}[htb!]
  \centering
  \begin{tabular}{lllllcccccc}
    $|\Omg|$ & $|I|$ & $|J|$ & obj1  & obj2 & time1 & time2 & nit1 & nit2 &
    nnd1 & nnd2 \\[3pt]
    \hline 
 30 & 10 & 10 &  0.5245 &  0.5245 &  0.1102 &  0.0010 &    5648  &     44 &     726  &      0 \\
 30 & 10 & 20 &  2.2719 &  2.2719 &  0.8049 &  0.0018 &   28550  &     47 &    4145  &      0 \\
 30 & 10 & 30 &  2.6131 &  2.6131 &  3.2642 &  0.0024 &  102087  &     62 &   14001  &      0 \\
 30 & 10 & 40 &  5.1586 &  5.1586 &  5.6163 &  0.0033 &  131596  &     76 &   19196  &      0 \\
 30 & 10 & 50 &  5.0001 &  5.0001 &  9.0805 &  0.0043 &  195253  &     90 &   22846  &      0 \\[3pt]
 
 30 & 20 & 10 &  0.5016 &  0.5016 &  0.3223 &  0.0013 &   10989  &     37 &    2539  &      0 \\
 30 & 20 & 20 &  1.2066 &  1.2066 &  0.9145 &  0.0022 &   29388  &     47 &    3740  &      0 \\
 30 & 20 & 30 &  1.8453 &  1.8453 &  1.6743 &  0.0034 &   48105  &     61 &    4558  &      0 \\
 30 & 20 & 40 &  3.2337 &  3.2337 &  5.1405 &  0.0045 &  103095  &     73 &   11907  &      0 \\
 30 & 20 & 50 &  3.8275 &  3.8275 & 17.1894 &  0.0060 &  290369  &     88 &   32039  &      0 \\[3pt]

 30 & 30 & 10 &  0.5157 &  0.5157 &  0.3663 &  0.0017 &   11164  &     45 &    2125  &      0 \\
 30 & 30 & 20 &  0.6535 &  0.6535 &  1.0768 &  0.0029 &   29061  &     50 &    3405  &      0 \\
 30 & 30 & 30 &  1.0014 &  1.0014 &  2.1576 &  0.0048 &   43994  &     57 &    4359  &      0 \\
 30 & 30 & 40 &  1.5006 &  1.5006 &  5.0494 &  0.0062 &   83450  &     68 &    7068  &      0 \\
 30 & 30 & 50 &  2.2996 &  2.2996 &  9.8038 &  0.0080 &  125315  &     88 &   11142  &      0 \\[3pt]

 30 & 40 & 10 &  0.3534 &  0.3534 &  0.3589 &  0.0019 &    9800  &     40 &    1947  &      0 \\
 30 & 40 & 20 &  0.5955 &  0.5955 &  1.1437 &  0.0036 &   29849  &     49 &    3187  &      0 \\
 30 & 40 & 30 &  0.7382 &  0.7382 &  8.5145 &  0.0056 &  130544  &     60 &   19287  &      0 \\
 30 & 40 & 40 &  1.4129 &  1.4129 &  7.0977 &  0.0075 &   99524  &     69 &   10759  &      0 \\
 30 & 40 & 50 &  1.6189 &  1.6189 & 18.5515 &  0.0096 &  184755  &     77 &   23746  &      0 \\[3pt]

 30 & 50 & 10 &  0.2517 &  0.2517 &  0.5710 &  0.0024 &   17061  &     42 &    2605  &      0 \\
 30 & 50 & 20 &  0.5661 &  0.5661 &  2.5842 &  0.0044 &   47038  &     48 &    7698  &      0 \\
 30 & 50 & 30 &  0.4230 &  0.4230 &  4.7255 &  0.0066 &   61234  &     61 &    9718  &      0 \\
 30 & 50 & 40 &  0.6475 &  0.6475 & 20.9926 &  0.0091 &  203931  &     66 &   32691  &      0 \\
 30 & 50 & 50 &  1.0046 &  1.0046 & 26.3588 &  0.0111 &  249046  &     82 &   28243  &      0 \\[3pt]
  \end{tabular}
  \caption{$|\Omg|=30$}
\end{table}

\begin{table}[htb!]
  \centering
  \begin{tabular}{lllllcccccc}
    $|\Omg|$ & $|I|$ & $|J|$ & obj1  & obj2 & time1 & time2 & nit1 & nit2 &
    nnd1 & nnd2 \\[3pt]
    \hline 
 40  & 10  &  10  &   1.3435  &   1.3435 &    1.2905  &   0.0012 &     59676  &       46 &     10526   &       0  \\     
 40  & 10  &  20  &   2.0444  &   2.0444 &    4.3158  &   0.0022 &    147108  &       61 &     19892   &       0  \\     
 40  & 10  &  30  &   2.7733  &   2.7733 &   22.8328  &   0.0033 &    659727  &       72 &     73049   &       0  \\     
 40  & 10  &  40  &   4.3808  &   4.3808 &  140.3831  &   0.0045 &   2482303  &       79 &    389523   &       0  \\     
 40  & 10  &  50  &   4.7360  &   4.7360 &   98.5991  &   0.0057 &   1825291  &       95 &    182072   &       0  \\[3pt]
                                                                                                                         
 40  & 20  &  10  &   0.5329  &   0.5329 &    0.7928  &   0.0017 &     31750  &       46 &      4682   &       0  \\     
 40  & 20  &  20  &   1.0413  &   1.0413 &   13.3224  &   0.0032 &    296554  &       59 &     54155   &       0  \\     
 40  & 20  &  30  &   1.1838  &   1.1838 &   18.4173  &   0.0048 &    367178  &       65 &     42918   &       0  \\     
 40  & 20  &  40  &   2.0741  &   2.0741 &   58.3325  &   0.0066 &    939497  &       83 &     97821   &       0  \\     
 40  & 20  &  50  &   3.0841  &   3.0841 &   50.4011  &   0.0088 &    686836  &       95 &     58319   &       0  \\[3pt]
                                                                                                                         
 40  & 30  &  10  &   0.5953  &   0.5953 &    1.7454  &   0.0022 &     54347  &       53 &      9491   &       0  \\     
 40  & 30  &  20  &   0.9238  &   0.9238 &    4.1242  &   0.0041 &     91838  &       64 &      9711   &       0  \\     
 40  & 30  &  30  &   1.3658  &   1.3658 &  141.3215  &   0.0064 &   1824573  &       64 &    247399   &       0  \\     
 40  & 30  &  40  &   1.8054  &   1.8054 &  115.7021  &   0.0091 &   1295503  &       88 &    130921   &       0  \\     
 40  & 30  &  50  &   1.9741  &   1.9741 &  280.7656  &   0.0114 &   2335817  &       92 &    283256   &       0  \\[3pt]
                                                                                                                         
 40  & 40  &  10  &   0.3047  &   0.3047 &    0.5463  &   0.0026 &     18789  &       55 &      1957   &       0  \\     
 40  & 40  &  20  &   0.5225  &   0.5225 &   21.1445  &   0.0051 &    359846  &       59 &     56909   &       0  \\     
 40  & 40  &  30  &   0.4173  &   0.4173 &   54.8075  &   0.0077 &    781976  &       68 &     90836   &       0  \\     
 40  & 40  &  40  &   1.2663  &   1.2663 &  145.8253  &   0.0109 &   1516330  &       80 &    166389   &       0  \\     
 40  & 40  &  50  &   1.2056  &   1.2056 &   50.3131  &   0.0141 &    466075  &       89 &     35755   &       0  \\[3pt]
                                                                                                                         
 40  & 50  &  10  &   0.1828  &   0.1828 &    1.0569  &   0.0032 &     31990  &       49 &      3986   &       0  \\     
 40  & 50  &  20  &   0.4907  &   0.4907 &   23.0135  &   0.0062 &    360601  &       60 &     51923   &       0  \\     
 40  & 50  &  30  &   0.7228  &   0.7228 &   26.4011  &   0.0093 &    349575  &       67 &     35394   &       0  \\     
 40  & 50  &  40  &   0.9797  &   0.9797 &  104.0897  &   0.0130 &    910488  &       76 &     96311   &       0  \\     
 40  & 50  &  50  &   1.0573  &   1.0573 &  240.1056  &   0.0181 &   1574056  &       93 &    169512   &       0  \\[3pt]
     
  \end{tabular}
  \caption{$|\Omg|=40$}
\end{table}



\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
